package cn.com.se.集合;


public class 链表回路问题 {

    public static class LinkedList{
        int data;
        LinkedList next;

        public LinkedList(int data){
            this.data = data;
            this.next = null;
        }
    }


    public static LinkedList isCyclicLinkedList(LinkedList head){
        if(head == null){
            return null;
        }

        LinkedList pOne = head; // one step per move
        LinkedList pTwo = head; // two step per move

        if(pTwo.next != null){
            pTwo = pTwo.next.next;
        } else {
            return null;
        }
        pOne = pOne.next;

        while(pTwo != pOne){
            if(pTwo != null && pTwo.next != null){
                pTwo = pTwo.next.next;
            } else{
                return null;
            }

            pOne = pOne.next;
        }

        while(head != pOne){
            pOne = pOne.next;
            head = head.next;
        }

        return pOne;
    }
}
